package com.itheima.leetcode.od.b.binarytree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * (B卷,200分)- 完全二叉树非叶子部分后序遍历（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出。
 * <p>
 * 1、只有一个节点的树，此节点认定为根节点（非叶子）。
 * <p>
 * 2、此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况
 * <p>
 * 其他说明：二叉树的后序遍历是基于根来说的，遍历顺序为：左-右-根
 * <p>
 * 输入描述
 * <p>
 * 一个通过空格分割的整数序列字符串
 * <p>
 * 输出描述
 * <p>
 * 非叶子部分树结构。备注：输出数字以空格分隔
 * <p>
 * 用例
 * <p>
 * 输入	1 2 3 4 5 6 7
 * 输出	2 3 1
 * 说明	找到非叶子部分树结构，然后采用后序遍历输出。
 */
public class CompleteBinaryTreeNonLeafPartPostTraversal {
    public static void main(String[] args) {
        /*//处理输入
        Scanner in=new Scanner(System.in);
        List<Integer> nums =Arrays.stream(in.nextLine().split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());*/

        int[] nums = Arrays.stream("1 2 3 4 5 6 7".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(nums));

    }

    public static String getResult(int[] nums) {
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }

        ArrayList<Integer> res = new ArrayList<>();
        dfs(nums, 0, res);

        return res.stream().map(String::valueOf).collect(Collectors.joining(" "));
    }

    /**
     * 非叶子部分后序遍历
     *
     * @param nums
     * @param root
     * @param res
     */
    public static void dfs(int[] nums, int root, ArrayList<Integer> res) {
        int left = root * 2 + 1;
        int right = root * 2 + 2;

        if (nums.length > left) {
            dfs(nums, left, res);
            if (nums.length > right) {
                dfs(nums, right, res);
            }
            res.add(nums[root]);
        }
    }
}
